package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * 先想一种呆算法, nlog排序, n空间
 * 然后还是 错误写法
 * <p>
 * - 排序然后swap,
 * 1 2 3 4 5 6
 * 2 1 4 3 6 5
 * 相等怎么办 1 1 3
 * 小一半大一半混着插
 * 0 1 2 3 | 4 5 6 7
 * 0 4 1 5 2 6 3 7
 * <p>
 * 奇数个
 * 0 1 2 3 4
 * 0 3 1 4 2
 * <p>
 * 0 1 2 3 | 4 5 6 7
 * 0 4 2 3 | 1 5 6 7
 * 0 4 1 5 | 2 3 6 7
 * 0 4 1 5 | 2 6 3 7
 * ---------
 * 0 1 2 3 | 4 5 6 7
 * <p>
 * 1111222
 * 0 1 2 3 4
 *
 * @author tzp
 * @since 2020/10/30
 */
public class LC324 implements Unknown {
    public void wiggleSort(int[] nums) {
        if (nums.length <= 1) return;
        Arrays.sort(nums);
        int[] target = new int[nums.length];
        int mid = (nums.length - 1) / 2;
        for (int i = 0; i < nums.length; i++) {
            if (i <= mid) {
                target[i * 2] = nums[i];
            } else {
                int index = (i - mid) * 2 - 1;
                target[index] = nums[i];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = target[i];
        }
    }

    public static void main(String[] args) {
//        int[] a = {0, 1, 2, 3, 4, 5};
//        int[] a = {1, 1, 2, 1, 2, 2, 1};
//        int[] a = {1, 1, 2, 1, 2, 2, 1, 2};
//        int[] a = {4, 5, 5, 6};
        int[] a = {1, 5, 5, 5, 6, 7};
        new LC324().wiggleSort(a);
        System.out.println(Arrays.toString(a));
    }
}
